"""
quicksort_v1
实验指导书上的快排算法
"""
import os
import random
from utils import is_ordered
from dataset import load_dataset


def rand_partition_v4(sequence, p, r):
    i = random.randint(p, r)
    sequence[r], sequence[i] = sequence[i], sequence[r]
    x = sequence[r]

    equal_replace1 = 0
    equal_replace2 = 0

    def replace1():
        nonlocal equal_replace1
        equal_replace1 = (equal_replace1 + 1) % 10
        return equal_replace1 % 30 == 0

    def replace2():
        nonlocal equal_replace2
        equal_replace2 = (equal_replace2 + 1) % 10
        return equal_replace2 % 30 == 0

    j = p
    k = r
    while j < k:
        # while j < k and (sequence[j] <= x or sequence[k] >= x):
        #     if sequence[j] <= x:
        #         j += 1
        #     if j < k and sequence[k] >= x:
        #         k -= 1
        # while j < k and (sequence[j] < x or sequence[j] == x and not replace1()):
        #     j += 1
        # while j < k and (sequence[k] > x or sequence[k] == x and not replace2()):
        #     k -= 1
        while j < k and (sequence[j] <= x):
            j += 1
        while j < k and (sequence[k] >= x):
            k -= 1
        sequence[j], sequence[k] = sequence[k], sequence[j]
    sequence[k], sequence[r] = x, sequence[k]
    return k


def _quicksort_v4(sequence, p, r):
    if p < r:
        q = rand_partition_v4(sequence, p, r)
        _quicksort_v4(sequence, p, q - 1)
        _quicksort_v4(sequence, q + 1, r)


def quicksort_v4(sequence):
    _quicksort_v4(sequence, 0, len(sequence) - 1)


if __name__ == '__main__':
    import time

    s = load_dataset(os.path.join('datasets', 'dataset-0.txt'))
    # s = list(range(10))
    # s = [7, 8, 9, 5, 1, 4, 2, 3, 6, 0]
    # random.shuffle(s)
    # print('s:', s)
    start = time.time()
    quicksort_v4(s)
    elapsed = time.time() - start
    # print('sorted s:', s)
    print('sort success')
    print('consume:', elapsed)
    print('is ordered:', is_ordered(s))
